#include "VIHC.h"
#include<memory>
#include<string>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
VIHC::VIHC(void)
{
}


VIHC::~VIHC(void)
{
}

unique_ptr<int[]> VIHC::_Runnum(const string& data)
{
	unique_ptr<int[]> runnum(new int[RUN_MAX+1]());
	for(uint32_t i=0;i<data.length();)
	{
		int run=0;
		while(i<data.length()&&data.at(i)!='1'&&run<RUN_MAX)
		{
			run++;
			i++;
		}
		if(run<RUN_MAX)
		{
			runnum[run]++;
			i++;
			//cout<<run<<'\t';
		}
		else
		{
			runnum[run]++;
			//cout<<RUN_MAX<<'\t';
		}
	}
	//int sum=0;
	//for(int i=0;i<RUN_MAX;i++)
		//sum+=(i+1)*runnum[i];
	//sum+=runnum[RUN_MAX]*RUN_MAX;
	//cout<<"sum="<<sum<<endl;
	return runnum;
}

unique_ptr<string[]> VIHC::_Huffman(unique_ptr<int[]> runnum)
{
	//tree
	vector<int> cost,parent,lchild;
	for(int i=0;i<=RUN_MAX;i++)
	{
		cost.push_back(runnum[i]);
		parent.push_back(-1);
		lchild.push_back(0);
	}
	//for(auto &e:cost)cout<<e<<"\t";
		//cout<<endl;
	while(1)
	{
		auto p1=min_element(cost.begin(),cost.end());
		int x1=*p1;
		*p1=INT_MAX;
		auto p2=min_element(cost.begin(),cost.end());
		int x2=*p2;
		*p2=INT_MAX;
		if(x1==INT_MAX||x2==INT_MAX)
			break;
		parent.at(p1-cost.begin())=cost.size();
		parent.at(p2-cost.begin())=cost.size();
		lchild.at(p1-cost.begin())=1;
		cost.push_back(x1+x2);
		parent.push_back(-1);
		lchild.push_back(0);
	}
	//for(uint32_t i=0;i<cost.size();i++)
	//{
		//cout<<"["<<i<<"]"<<parent.at(i)<<")\t";
	//}
	//cout<<endl;
	//code
	unique_ptr<string[]> runcode(new string[RUN_MAX+1]);
	for(int i=0;i<=RUN_MAX;i++)
	{
		stack<char> _stack;
		int cur=i;
		while(parent.at(cur)!=-1)
		{
			if(lchild.at(cur))
				_stack.push('0');
			else
				_stack.push('1');
			cur=parent.at(cur);
		}
		while(!_stack.empty())
		{
			runcode[i]+=_stack.top();
			_stack.pop();
		}
		//cout<<runcode[i]<<endl;
	}
	return runcode;
}

unique_ptr<string> VIHC::code(const string& data)
{
	unique_ptr<string> _string(new string);
	unique_ptr<string[]> runcode=_Huffman(_Runnum(data));
	for(uint32_t i=0;i<data.length();)
	{
		int run=0;
		while(i<data.length()&&data.at(i)!='1'&&run<RUN_MAX)
		{			
			run++;
			i++;
		}
		if(run<RUN_MAX)
		{
			_string->append(runcode[run]);
			i++;
		}
		else
		{
			_string->append(runcode[run]);
		}
	}
	return _string;
}
